import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序算法
 * 思路：双重for循环，内层循环每执行完一次，就会从剩下元素中选择一个最小的元素，然后将其和待排序数组的第一个元素交换位置，这样外层
 *      循环结束后，所有的元素都是从小到大顺序排列了。
 * 时间复杂度：O(n^2)
 * 最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧!
 * @author HuRui
 * create on 2018/12/23 15:25
 */
public class SelectionSort {

    private SelectionSort() {
    }
    /**
     * 选择排序
     * @param arr 待排序数组
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            //假如待排序数组的第一个元素为最小值
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            DataUtil.swap(arr,i,minIndex);
        }
    }

    public static void sort1(Integer[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            DataUtil.swap(arr,i,minIndex);
        }
    }

    /**
     * 选择排序的升级版本
     * @param arr
     */
    public static void sort(Comparable[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            //假如待排序数组的第一个元素为最小值
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (arr[j].compareTo(arr[minIndex])<0) {
                    minIndex = j;
                }
            }
            DataUtil.swap(arr,i,minIndex);
        }
    }



    public static void main(String[] args){
        Integer[] arr = DataUtil.randomArray(10, 0, 100);
        System.out.println("排序前：");
        DataUtil.printArray(arr);
        long l = System.currentTimeMillis();
        SelectionSort.sort1(arr);
        long l1 = System.currentTimeMillis();
        System.out.println("耗时：" +(l1 - l));
        System.out.println("排序后：");
        DataUtil.printArray(arr);
    }
}
